Cheatsheets

Data Structure and Algorithms

July 27, 2024

Algorithms

Sorting

Bubble Sort - A sorting algorithm that compares two adjacent elements and swaps them until they are in the intended order.

function bubbleSort(array) {
  // Loop to access each array element
  for (let i = 0; i < array.length; i++) {
    // Loop to compare array elements
    for (let j = 0; j < array.length - i - 1; j++) {
      // Compare two adjacent elements
      // Change > to < to sort in descending order
      if (array[j] > array[j + 1]) {
        // Swapping elements if elements
        // are not in the intended order
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

let data = [-2, 45, 0, 11, -9];
bubbleSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(data);

Insertion Sort - Iterates through an array, comparing elements and moving them into their correct positions one by one.

function insertionSort(array) {
  // Loop through the entire array
  for (let i = 1; i < array.length; i++) {
    let j = i - 1;
    let temp = array[i];
    // Compare the current element with the next one
    while (j >= 0 && array[j] > temp) {
      // If the current element is greater, move it back
      array[j + 1] = array[j];
      j--;
    }
    // Insert the current element at its correct position
    array[j + 1] = temp;
  }
}

let data = [-2, 45, 0, 11, -9];
insertionSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(data);

Selection Sort - Divides the array into sorted and unsorted parts, repeatedly selects the smallest element from the unsorted portion and places it at the beginning of the sorted part.

function selectionSort(array) {
  // Loop through the entire array
  for (let i = 0; i < array.length; i++) {
    let min = i;
    // Find the index of the minimum element
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[min]) {
        min = j;
      }
    }
    // Swap the minimum element with the first element
    let temp = array[i];
    array[i] = array[min];
    array[min] = temp;
  }
}

let data = [-2, 45, 0, 11, -9];
selectionSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(data);

Merge Sort - It is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm.

function mergeSort(array) {
  if (array.length > 1) {
    // Split the array into two halves
    const r = Math.floor(array.length / 2);
    const L = array.slice(0, r);
    const M = array.slice(r);

    // Sort the two halves
    mergeSort(L);
    mergeSort(M);

    let i = 0;
    let j = 0;
    let k = 0;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at A[p..r]
    while (i < L.length && j < M.length) {
      if (L[i] < M[j]) {
        array[k] = L[i];
        i += 1;
      } else {
        array[k] = M[j];
        j += 1;
      }
      k += 1;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < L.length) {
      array[k] = L[i];
      i += 1;
      k += 1;
    }

    while (j < M.length) {
      array[k] = M[j];
      j += 1;
      k += 1;
    }
  }
}

// Print the array
function printList(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
}

// Driver program
const array = [6, 5, 12, 10, 9, 1];

mergeSort(array);

console.log("Sorted array is: ");
printList(array);

Quick Sort - A divide-and-conquer algorithm that divides an array into smaller sub-arrays and sorts them recursively.

function quickSort(array, left, right) {
  if (left < right) {
    let pivot = partition(array, left, right);

    // Recursively sort elements around the pivot
    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
  }
}

function partition(array, left, right) {
  let pivot = array[right];
  let i = left - 1;

  for (let j = left; j < right; j++) {
    if (array[j] < pivot) {
      i++;
      // Swap elements at i and j
      let temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
  }

  // Swap elements at i+1 and right
  let temp = array[i + 1];
  array[i + 1] = array[right];
  array[right] = temp;

  return i + 1;
}

let data = [-2, 45, 0, 11, -9];
quickSort(data, 0, data.length - 1);

console.log("Sorted Array in Ascending Order:");
console.log(data);

Heap Sort - Utilizes a binary heap data structure to sort elements in an array by repeatedly selecting the maximum element from the heap.

function heapSort(array) {
  let n = array.length;

  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(array, n, i);
  }

  // Heap sort
  for (let i = n - 1; i > 0; i--) {
    // Swap root with the last element
    let temp = array[0];
    array[0] = array[i];
    array[i] = temp;

    // Heapify the reduced heap
    heapify(array, i, 0);
  }
}

function heapify(array, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left < n && array[left] > array[largest]) {
    largest = left;
  }

  if (right < n && array[right] > array[largest]) {
    largest = right;
  }

  if (largest !== i) {
    let temp = array[i];
    array[i] = array[largest];
    array[largest] = temp;

    heapify(array, n, largest);
  }
}

let data = [-2, 45, 0, 11, -9];
heapSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(data);

Counting Sort - Suitable for sorting integers when the range of input is known. It counts the occurrences of each element and places them in order.

function countingSort(array) {
  let size = array.length;
  let output = new Array(size);
  let count = new Array(256);
  let max = array[0];

  for (let i = 1; i < size; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }

  for (let i = 0; i <= max; ++i) {
    count[i] = 0;
  }

  for (let i = 0; i < size; i++) {
    count[array[i]]++;
  }

  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  for (let i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

  for (let i = 0; i < size; i++) {
    array[i] = output[i];
  }
}

let data = [4, 2, 2, 8, 3, 3, 1];
countingSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(data);

Radix Sort - Sorts integers by processing individual digits, typically starting from the least significant digit to the most significant.

function radixSort(array) {
  const getMax = (array) => {
    let max = 0;
    for (let num of array) {
      max = Math.max(max, num);
    }
    return max;
  };

  const digitCount = (num) => {
    if (num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num))) + 1;
  };

  const mostDigits = (array) => {
    let maxDigits = 0;
    for (let num of array) {
      maxDigits = Math.max(maxDigits, digitCount(num));
    }
    return maxDigits;
  };

  let maxDigits = mostDigits(array);
  for (let k = 0; k < maxDigits; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < array.length; i++) {
      let digit = Math.floor(Math.abs(array[i]) / Math.pow(10, k)) % 10;
      buckets[digit].push(array[i]);
    }
    array = [].concat(...buckets);
  }

  return array;
}

let data = [170, 45, 75, 90, 802, 24, 2, 66];
let result = radixSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(result);

Bucket Sort - Distributes elements into different "buckets" and then sorts these buckets individually, usually using another sorting algorithm or technique.

function bucketSort(array, bucketSize = 5) {
  if (array.length === 0) {
    return array;
  }

  let min = array[0];
  let max = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] < min) {
      min = array[i];
    } else if (array[i] > max) {
      max = array[i];
    }
  }

  let bucketCount = Math.floor((max - min) / bucketSize) + 1;
  let buckets = new Array(bucketCount);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  for (let i = 0; i < array.length; i++) {
    buckets[Math.floor((array[i] - min) / bucketSize)].push(array[i]);
  }

  array.length = 0;
  for (let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]);
    for (let j = 0; j < buckets[i].length; j++) {
      array.push(buckets[i][j]);
    }
  }

  return array;
}

let data = [4, 2, 2, 8, 3, 3, 1];
let result = bucketSort(data);

console.log("Sorted Array in Ascending Order:");
console.log(result);

Searching

Linear Search - Iterates through a list sequentially to find a target element.

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

let data = [2, 3, 4, 10, 40];
let target = 10;
let result = linearSearch(data, target);

if (result !== -1) {
  console.log("Element found at index:", result);
} else {
  console.log("Element not found in the array");
}

Binary Search - Requires a sorted array and repeatedly divides the search interval in half until the target element is found or the search space is exhausted.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);

    if (array[mid] === target) {
      return mid;
    }

    if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

let data = [2, 3, 4, 10, 40];
let target = 10;
let result = binarySearch(data, target);

if (result !== -1) {
  console.log("Element found at index:", result);
} else {
  console.log("Element not found in the array");
}

Depth-first Search (DFS) - Traverses a graph or tree by going as far as possible along a branch before backtracking.

function dfs(graph, node, visited) {
  if (!visited[node]) {
    console.log(node);
    visited[node] = true;
    for (let i = 0; i < graph[node].length; i++) {
      dfs(graph, graph[node][i], visited);
    }
  }
}

let graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};
let visited = {};

dfs(graph, 2, visited);

Breadth-first Search (BFS) - Explores all neighbor nodes at the present depth level before moving on to nodes at the next depth level.

function bfs(graph, start) {
  let visited = {};
  let queue = [start];

  while (queue.length > 0) {
    let node = queue.shift();
    if (!visited[node]) {
      console.log(node);
      visited[node] = true;
      for (let i = 0; i < graph[node].length; i++) {
        queue.push(graph[node][i]);
      }
    }
  }
}

let graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};

bfs(graph, 2);

Best-first Search - An informed search algorithm that uses a heuristic to determine the most promising node to explore next.

function bestFirstSearch(graph, start, goal) {
  let visited = {};
  let queue = [start];

  while (queue.length > 0) {
    let node = queue.shift();
    if (node === goal) {
      console.log("Goal node found");
      return;
    }
    if (!visited[node]) {
      console.log(node);
      visited[node] = true;
      for (let i = 0; i < graph[node].length; i++) {
        queue.push(graph[node][i]);
      }
      queue.sort((a, b) => heuristic(a, goal) - heuristic(b, goal));
    }
  }
}

function heuristic(node, goal) {
  // Heuristic function to estimate the distance from node to goal
  return Math.abs(node - goal);
}

let graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};

bestFirstSearch(graph, 2, 3);

Ternary Search - Divides the search space into three parts instead of two in binary search, useful in sorted and uniformly distributed arrays.

function ternarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid1 = left + Math.floor((right - left) / 3);
    let mid2 = right - Math.floor((right - left) / 3);

    if (array[mid1] === target) {
      return mid1;
    }

    if (array[mid2] === target) {
      return mid2;
    }

    if (target < array[mid1]) {
      right = mid1 - 1;
    } else if (target > array[mid2]) {
      left = mid2 + 1;
    } else {
      left = mid1 + 1;
      right = mid2 - 1;
    }
  }

  return -1;
}

let data = [2, 3, 4, 10, 40];
let target = 10;
let result = ternarySearch(data, target);

if (result !== -1) {
  console.log("Element found at index:", result);
} else {
  console.log("Element not found in the array");
}

Interpolation Search - An improved variant of binary search that works better for uniformly distributed arrays by using interpolation to find the probable position of the target element.

function interpolationSearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right && target >= array[left] && target <= array[right]) {
    let pos = left + Math.floor(
      ((right - left) / (array[right] - array[left])) * (target - array[left])
    );

    if (array[pos] === target) {
      return pos;
    }

    if (array[pos] < target) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }

  return -1;
}

let data = [2, 3, 4, 10, 40];
let target = 10;
let result = interpolationSearch(data, target);

if (result !== -1) {
  console.log("Element found at index:", result);
} else {
  console.log("Element not found in the array");
}

Exponential Search - Exploits the property of binary search to find the range in which the target element lies, followed by a binary search in that range.

function exponentialSearch(array, target) {
  let n = array.length;
  if (array[0] === target) {
    return 0;
  }

  let i = 1;
  while (i < n && array[i] <= target) {
    i = i * 2;
  }

  return binarySearch(array, target, i / 2, Math.min(i, n - 1));
}

function binarySearch(array, target, left, right) {
  if (right >= left) {
    let mid = left + Math.floor((right - left) / 2);

    if (array[mid] === target) {
      return mid;
    }

    if (array[mid] > target) {
      return binarySearch(array, target, left, mid - 1);
    }

    return binarySearch(array, target, mid + 1, right);
  }

  return -1;
}

let data = [2, 3, 4, 10, 40];
let target = 10;
let result = exponentialSearch(data, target);

if (result !== -1) {
  console.log("Element found at index:", result);
} else {
  console.log("Element not found in the array");
}

Divide and Conquer

Breaks a problem into smaller, more manageable sub-problems until they become simple enough to solve directly.

function divideAndConquer(problem, params) {
  // Base case
  if (problem is simple) {
    return simpleSolution(problem);
  }

  // Divide the problem into subproblems
  subproblems = splitProblem(problem, data);

  // Recursively solve each subproblem
  solutions = [];
  for (subproblem in subproblems) {
    solutions.push(divideAndConquer(subproblem, params));
  }

  // Combine the solutions
  result = combineSolutions(solutions);
  return result;
}

let problem = "problem";
let params = "params";
let result = divideAndConquer(problem, params);

console.log(result);

Backtracking

A methodical way to explore all possible configurations in a search space to find a solution.

function backtracking(candidate, params) {
  if (candidate is a solution) {
    output(candidate);
    return;
  }

  for (next in list) {
    if (isValid(next, candidate)) {
      place(next, candidate);
      backtracking(candidate, params);
      remove(next, candidate);
    }
  }
}

let candidate = "candidate";
let params = "params";
backtracking(candidate, params);

console.log(result);

Recursion

Solves problems by breaking them down into smaller instances of the same problem.

function recursiveFunction(input) {
  if (input <= 0) {
    return input;
  } else {
    return recursiveFunction(input - 1);
  }
}

let input = 5;
let result = recursiveFunction(input);

console.log(result);

Dynamic Programming

Solves problems by breaking them down into simpler overlapping sub-problems, and storing the results to avoid redundant computations.

Data Structure

Array - A collection of elements stored at contiguous memory locations.

let array = [1, 2, 3, 4, 5];
console.log(array);

String - A sequence of characters.

let string = "Hello, World!";
console.log(string);

Linked List - A linear collection of elements where each element points to the next one.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  insert(data) {
    let newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  display() {
    let current = this.head;
    while (current !== null) {
      console.log(current.data);
      current = current.next;
    }
  }
}

let list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.display();

console.log(list);

Matrix/Grid - A 2-dimensional array often representing rows and columns of elements.

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
console.log(matrix);

Stack - A Last-In-First-Out (LIFO) data structure where elements are inserted and removed from the same end.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.items.length === 0) {
      return "Underflow";
    }
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.isEmpty());

Queue - A First-In-First-Out (FIFO) data structure where elements are inserted at the rear and removed from the front.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.items.length === 0) {
      return "Underflow";
    }
    return this.items.shift();
  }

  front() {
    if (this.items.length === 0) {
      return "No elements in Queue";
    }
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue());
console.log(queue.front());
console.log(queue.isEmpty());

Heap - A specialized tree-based data structure that satisfies the heap property (max-heap/min-heap).

class Heap {
  constructor() {
    this.items = [];
  }

  insert(element) {
    this.items.push(element);
    this.heapifyUp();
  }

  extract() {
    if (this.items.length === 0) {
      return "Underflow";
    }
    if (this.items.length === 1) {
      return this.items.pop();
    }

    let root = this.items[0];
    this.items[0] = this.items.pop();
    this.heapifyDown();
    return root;
  }

  heapifyUp() {
    let index = this.items.length - 1;
    while (index > 0) {
      let element = this.items[index];
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.items[parentIndex];
      if (element <= parent) {
        break;
      }
      this.items[index] = parent;
      this.items[parentIndex] = element;
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    let length = this.items.length;
    let element = this.items[0];

    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.items[leftChildIndex];
        if (leftChild > element) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.items[rightChildIndex];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) {
        break;
      }

      this.items[index] = this.items[swap];
      this.items[swap] = element;
      index = swap;
    }
  }
}

let heap = new Heap();
heap.insert(1);
heap.insert(2);
heap.insert(3);
console.log(heap.extract());

Hash - A data structure that maps keys to values, allowing for efficient retrieval, insertion, and deletion.

class HashTable {
  constructor() {
    this.table = [];
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37;
  }

  put(key, value) {
    let index = this.hash(key);
    this.table[index] = value;
  }

  get(key) {
    let index = this.hash(key);
    return this.table[index];
  }

  remove(key) {
    let index = this.hash(key);
    this.table[index] = undefined;
  }
}

let hashTable = new HashTable();
hashTable.put("John", 123);
hashTable.put("Doe", 456);
console.log(hashTable.get("John"));
hashTable.remove("Doe");

Tree - A hierarchical data structure composed of nodes, each having a value and references to its child nodes.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  inorder(node) {
    if (node !== null) {
      this.inorder(node.left);
      console.log(node.value);
      this.inorder(node.right);
    }
  }
}

let tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(4);
tree.insert(6);
tree.insert(8);
tree.inorder(tree.root);

console.log(tree);

Graph - A collection of nodes (vertices) connected by edges that represent relationships or connections between the nodes.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }

  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }

  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
}

let graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");
graph.removeEdge("A", "B");
graph.removeVertex("C");

console.log(graph);

This is a brief overview of some common algorithms and data structures. There are many more algorithms and data structures that can be explored and implemented in various programming languages.